﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace MaxProfit
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var demo = new MinMaxDemo();

            //load from a stored proc  order by datetime..
            //you could load an of objects instead of ints down below, but for the sake of demonstration...
            var stockPriceArrayOrderedByDateTime = new[] { 5, 6, 7, 8, 9, 10, 11, 12, 9, 7, 6, 15, 13, 14, 12, 19, 22, 29, 41, 42 };
            Console.WriteLine("MaxProfit: " + GetMaxProfit(demo, stockPriceArrayOrderedByDateTime));
            Console.WriteLine("Hit any key to continue"); //can't find the "Any" key?  ;)
            Console.ReadKey();

            //since we have parts of the algorithm broken out, we can test each piece of it..
            //because this console app won't allow Microsoft.VisualStudio.TestTools.UnitTesting to be added, then lets verify this way.

            List<Range> ascendingRanges = demo.GetRangesOfAscendingNumbers(stockPriceArrayOrderedByDateTime);
            var verifyRange1 = ascendingRanges[0].Min.Value == 5 && ascendingRanges[0].Max.Value == 12;
            var verifyRange2 = ascendingRanges[1].Min.Value == 6 && ascendingRanges[1].Max.Value == 15;
            var verifyRange3 = ascendingRanges[2].Min.Value == 13 && ascendingRanges[2].Max.Value == 14;
            var verifyRange4 = ascendingRanges[3].Min.Value == 12 && ascendingRanges[3].Max.Value == 42;

            if (!(verifyRange1 && verifyRange2 && verifyRange3 && verifyRange4) && ascendingRanges.Count == 4)
            {
                throw new Exception("oops..");
            }

            //each method in MinMaxDemo() could also be tested for behavior if time allows.

            //---

            //using different sets of data, testing just the part that comes up with the ranges

            var stockPriceArrayOrderedByDateTime2 = new[] {5, 6, 12, 8, 9, 10, 3, 14, 12, 19, 22, 29, 41, 1};

            List<Range> ascendingRanges2 = demo.GetRangesOfAscendingNumbers(stockPriceArrayOrderedByDateTime2);
            var verifyRange5 = ascendingRanges2[0].Min.Value == 5 && ascendingRanges2[0].Max.Value == 12;
            var verifyRange6 = ascendingRanges2[1].Min.Value == 8 && ascendingRanges2[1].Max.Value == 10;
            var verifyRange7 = ascendingRanges2[2].Min.Value == 3 && ascendingRanges2[2].Max.Value == 14;
            var verifyRange8 = ascendingRanges2[3].Min.Value == 12 && ascendingRanges2[3].Max.Value == 41;
            //remove item #5
            if (!(verifyRange5 && verifyRange6 && verifyRange7 && verifyRange8) && ascendingRanges2.Count == 4)
            {
                throw new Exception("oops..");
            }

            var stockPriceArrayOrderedByDateTime3 = new[] { 5, 6, 7, 8, 9, 10, 11, 12, 8, 8, 8, 8, 13, 14, 12, 19, 22, 17, 41, 42, 11, 11, 32, 17, 41, 1 };

            List<Range> ascendingRanges3 = demo.GetRangesOfAscendingNumbers(stockPriceArrayOrderedByDateTime3);
            var verifyRange9 = ascendingRanges3[0].Min.Value == 5 && ascendingRanges3[0].Max.Value == 12;
            var verifyRange10 = ascendingRanges3[1].Min.Value == 8 && ascendingRanges3[1].Max.Value == 14;
            var verifyRange11 = ascendingRanges3[2].Min.Value == 12 && ascendingRanges3[2].Max.Value == 22;
            var verifyRange12 = ascendingRanges3[3].Min.Value == 17 && ascendingRanges3[3].Max.Value == 42;
            var verifyRange13 = ascendingRanges3[4].Min.Value == 11 && ascendingRanges3[4].Max.Value == 32;
            var verifyRange14 = ascendingRanges3[5].Min.Value == 17 && ascendingRanges3[5].Max.Value == 41;

            if (!(verifyRange9 && verifyRange10 && verifyRange11 && verifyRange12 && verifyRange13 && verifyRange14) && ascendingRanges3.Count == 6)
            {
                throw new Exception("oops..");
            }

        }

        private static int GetMaxProfit(MinMaxDemo demo, int[] stockPriceArrayOrderedByDateTime)
        {
            //1st pass
            List<Range> ascendingRanges = demo.GetRangesOfAscendingNumbers(stockPriceArrayOrderedByDateTime);

            //these ranges can also be checked by a unit test at this point, as GetRangesOfAscendingNumbers is its own method.

            //2nd pass.  Get the highest of what you collected.
            var maxProfit = ascendingRanges.Select(range => range.Max.Value - range.Min.Value).Max();
            return maxProfit;
        }
    }

    public class MinMaxDemo
    {
        public List<Range> GetRangesOfAscendingNumbers(int[] stockPriceArrayOrderedByDateTime)
        {
            var ranges = new List<Range>();

            var previousMin = new ArrayItem();
            var previousMax = new ArrayItem();

            var currentMin = new ArrayItem();
            var currentMax = new ArrayItem();

            int minMarkerLocation = 0;
            int maxMarkerLocation = 0;

            int locationInArray = 0;

            foreach (var price in stockPriceArrayOrderedByDateTime)
            {
                if (currentMin.Value == 0 || price < previousMin.Value)
                {
                    currentMin.location = locationInArray;
                    currentMin.Value = price;

                    //start over 
                    minMarkerLocation = locationInArray;
                    maxMarkerLocation = locationInArray;
                }

                if (price > currentMax.Value || currentMax.Value > previousMax.Value || previousMax.Value == 0)
                {
                    currentMax.location = locationInArray;
                    currentMax.Value = price;

                    maxMarkerLocation = locationInArray;
                }

                if (locationInArray < stockPriceArrayOrderedByDateTime.Length)
                {
                    if (this.IsAMaxValue(currentMin, currentMax, 
                                         minMarkerLocation, maxMarkerLocation,
                                         price, stockPriceArrayOrderedByDateTime, locationInArray))
                    {
                        if (this.IsANewRange(currentMin, currentMax, previousMin))
                        { 
                            currentMin = this.CreateAndAddRange(currentMin, currentMax, ranges, ref minMarkerLocation);
                        }
                    }
                }

                currentMax = new ArrayItem();

                previousMin = currentMin;
                previousMax = currentMax;

                locationInArray += 1;
            }

            return ranges;
        }
         
        private bool IsAMaxValue(ArrayItem currentMin, ArrayItem currentMax, int minMarkerLocation, int maxMarkerLocation, int price, int [] stockPriceArrayOrderedByDateTime, int locationInArray)
        {
            if (locationInArray + 1 == stockPriceArrayOrderedByDateTime.Length &&
                currentMax.Value >= currentMin.Value)
            {
                return true; //because we are at the end.  

                //todo: there might be a corner case here that needs to be addressed.
            }
            else
            {
                int nextPrice = stockPriceArrayOrderedByDateTime[locationInArray + 1];

                return maxMarkerLocation > minMarkerLocation &&
                       nextPrice < price &&
                       currentMax.Value >= currentMin.Value;
            }
        }

        private bool IsANewRange(ArrayItem currentMin, ArrayItem currentMax, ArrayItem previousMin)
        {
            return currentMin != new ArrayItem() &
                   currentMax != new ArrayItem() &
                   currentMin.location >= previousMin.location &
                   currentMax.Value != 0 &
                   currentMax.Value != currentMin.Value;
        }

        private ArrayItem CreateAndAddRange(ArrayItem currentMin, 
                                            ArrayItem currentMax, 
                                            ICollection<Range> ranges,
                                            ref int minMarkerLocation)
        {
            var currentRange = new Range()
            {
                Min = new ArrayItem {location = currentMin.location, Value = currentMin.Value},
                Max = new ArrayItem {location = currentMax.location, Value = currentMax.Value},
            };

            ranges.Add(currentRange);

            minMarkerLocation = 0;
            currentMin = new ArrayItem();
            return currentMin;
        }
    }

    public class ArrayItem
    {
        public int location { get; set; }
        public int Value { get; set; }
    }

    public class Range
    {
        public ArrayItem Min { get; set; }
        public ArrayItem Max { get; set; }
    }
}